package chapter02_linkedList;

import java.util.Stack;

/**
 * 描述：
 *      判断链表是否是回文结构
 * @author hl
 * @date 2021/1/26 11:01
 */
public class IsPalindromel {
    /**
     * 让右部分链表反转，然后两个指针分别从左右两边同时遍历判断，判断完成后将原来的链表恢复
     * 时间复杂度O(n)，空间复杂度O(1)，用有限的三个变量完成
     * @param head
     * @return
     */
    public boolean isPalindromel3(ListNode head){
        if (head == null || head.next == null) {
            return true;
        }
        boolean res = true;
        //node1 -> leftStart, node2 -> rightStart
        ListNode node1 = head, node2 = head, node3 = null;
        while(node2.next != null && node2.next.next != null){
            node2 = node2.next.next;
            node1 = node1.next;//node1 -> 中部
        }
        node2 = node1.next;//右部分第一个
        node1.next = null;//node1 -> pre, node3 -> next
        while(node2 != null){
            //node1 -> next
            node3 = node2.next;
            node2.next = node1;
            node1 = node2;
            node2 = node3;
        }
        node3 = node1;//记录最右边的结点
        node2 = head;
        //判断回文
        while(node1 != null && node2 != null){
            if (node1.val != node2.val) {
                res = false;
                break;
            }
            node1 = node1.next;
            node2 = node2.next;
        }
        node2 = null;//pre
        //恢复原来的链表结构
        while(node3 != null){
            node1 = node3.next;//node1->next
            node3.next = node2;
            node2 = node3;
            node3 = node1;
        }
        return res;
    }

    public static void main(String[] args) {
        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        node.next.next = new ListNode(2);
        node.next.next.next = new ListNode(1);
        new IsPalindromel().isPalindromel3(node);

    }


    /**
     * 右半部分压入栈，优雅
     * @param head
     * @return
     */
    public boolean isPalindromel2(ListNode head){
        if (head == null || head.next == null) {
            return true;
        }
        ListNode cur = head;
        //最终为中间结点的下一个结点
        ListNode right = head.next;
        while(cur.next != null && cur.next.next != null){
            cur = cur.next.next;
            right = right.next;
        }
        Stack<ListNode> stack = new Stack<>();
        while(right != null){
            stack.push(right);
            right = right.next;
        }
        cur = head;
        while(!stack.isEmpty()){
            if (stack.pop().val != cur.val) {
                return false;
            }
            cur = cur.next;
        }
        return true;
    }

    /**
     * 左半部分压入栈
     * @param head
     * @return
     */
    public boolean isPalindromel1(Node head){
        if (head == null || head.next == null) {
            return true;
        }
        Stack<Node> stack = new Stack<>();
        int len = 0;
        Node cur = head;
        while(cur != null){
            cur = cur.next;
            len++;
        }
        cur = head;
        for (int i = 0; i < len / 2; i++) {
            stack.push(cur);
            cur = cur.next;
        }
        cur = len % 2 == 0 ? cur : cur.next.next;
        while(cur != null){
            if (stack.isEmpty() || cur.val != stack.pop().val) {
                return false;
            }
            cur = cur.next;
        }
        return stack.isEmpty();
    }
}
